package dfs;

import org.junit.Test;

import java.util.Arrays;

public class NumberOfIslands200 {
    @Test
    public void test1() {
        char[][] g = new char[][]{
                {'1','1','1','1','1','0','1','1','1','1'},
                {'1','0','1','0','1','1','1','1','1','1'},
                {'0','1','1','1','0','1','1','1','1','1'},
                {'1','1','0','1','1','0','0','0','0','1'},
                {'1','0','1','0','1','0','0','1','0','1'},
                {'1','0','0','1','1','1','0','1','0','0'},
                {'0','0','1','0','0','1','1','1','1','0'},
                {'1','0','1','1','1','0','0','1','1','1'},
                {'1','1','1','1','1','1','1','1','0','1'},
                {'1','0','1','1','1','1','1','1','1','0'}
        };
        System.out.println(numIslands(g));
    }

    @Test
    public void test2() {
        char[][] g = new char[][]{
                {'1','1','0','0','0'},
                {'1','1','0','0','0'},
                {'0','0','1','0','0'},
                {'0','0','0','1','1'}
        };
        System.out.println(numIslands(g));
    }


    public int numIslands(char[][] g) {
        int[][] marks = new int[g.length][g[0].length];
        for (int[] mark : marks) {
            Arrays.fill(mark, 0);
        }
        int count = 0;
        for (int i = 0; i < marks.length; i++) {
            for (int j = 0; j < marks[i].length; j++) {
                if (g[i][j] == '1' && marks[i][j] == 0) {
                    count++;
                    searchAt(g, marks, i, j, count);
                }
            }
        }
        return count;
    }

    // pre required: i >= 0 && i < g.length && j >= 0 && j < g[i].length && g[i][j] == '1' && marks[i][j] == 0
    public void searchAt(char[][] g, int[][] marks, int i, int j, int count) {
        marks[i][j] = count;
        trySearchAt(g, marks, i-1, j, count);
        trySearchAt(g, marks, i+1, j, count);
        trySearchAt(g, marks, i, j-1, count);
        trySearchAt(g, marks, i, j+1, count);
    }

    public void trySearchAt(char[][] g, int[][] marks, int i, int j, int count) {
        if (i >= 0 && i < g.length && j >= 0 && j < g[i].length && g[i][j] == '1' && marks[i][j] == 0) {
            searchAt(g, marks, i, j, count);
        }
    }

    // 类似于并查集
    public int numIslandsWrong(char[][] g) {
        // 初始独立节点数量
        int count = 0;

        // 并查集
        int h = g.length;
        int w = g[0].length;
        int[] parent = new int[h*w];

        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                int flatIndex = getFlatIndex(w, i, j);
                parent[flatIndex] = Integer.MAX_VALUE;
                if (g[i][j] == '1') {
                    parent[flatIndex] = flatIndex;
                    if (i > 0 && g[i-1][j] == '1') {
                        parent[flatIndex] = Math.min(parent[flatIndex], parent[getFlatIndex(w, i-1, j)]);
                    }
                    if (j > 0 && g[i][j-1] == '1') {
                        parent[flatIndex] = Math.min(parent[flatIndex], parent[getFlatIndex(w, i, j-1)]);
                    }
                    if (parent[flatIndex] == flatIndex) {
                        count++;
                    }
                }
            }
        }

        for (int i = h-1; i >= 0; i--) {
            for (int j = w-1; j >= 0; j--) {
                int flatIndex = getFlatIndex(w, i, j);
                if (g[i][j] == '1') {
                    int oldParent = parent[flatIndex];
                    if (j < w-1 && g[i][j+1] == '1') {
                        parent[flatIndex] = Math.min(parent[flatIndex], parent[getFlatIndex(w, i, j+1)]);
                    }
                    if (i < h-1 && g[i+1][j] == '1') {
                        parent[flatIndex] = Math.min(parent[flatIndex], parent[getFlatIndex(w, i+1, j)]);
                    }
                    if (oldParent == flatIndex && parent[flatIndex] < oldParent) {
                        count--;
                    }
                }
            }
        }
        return count;
    }

    public int getFlatIndex(int w, int i, int j) {
        return i * w + j;
    }
}
